package lc.q101_150;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Q133 {

    class Node {
        public int val;
        public List<Node> neighbors;
        public Node() {
            val = 0;
            neighbors = new ArrayList<Node>();
        }
        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<Node>();
        }
        public Node(int _val, ArrayList<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    }

    private Map<Node,Node> visited = new HashMap<>();

    public Node cloneGraph(Node node) {
        // 如果子列表是空
        if (node == null) {
            return node;
        }
        if (visited.containsKey(node)) {
            // 访问过了
            return visited.get(node);
        }
        Node result = new Node(node.val);
        visited.put(node, result);
        if (node.neighbors == null) {
            return result;
        }
        result.neighbors = new ArrayList<>();
        for (Node neighbor : node.neighbors) {
            result.neighbors.add(cloneGraph(neighbor));
        }
        return result;
    }

}
